package com.banmoon.algorithm.order;

import java.util.Arrays;
import java.util.Random;

/**
 * 归并排序
 */
public class Demo06 {

    public static void main(String[] args) {
        int length = 10;
        int[] arr = new int[length];
        Random random = new Random();
        for (int i = 0; i < length; i++)
            arr[i] = random.nextInt(length);
        System.out.println("排序前的数组：" + Arrays.toString(arr));
        int[] sortArr = sort(arr, 0, arr.length-1);
        System.out.println("排序后的数组：" + Arrays.toString(sortArr));
    }

    public static int[] sort(int[] arr, int start, int end){
        if(start<end){
            // 找到中间的下标
            int mid = (start +end)/2;
            // 开始至中间，为一个数组，进行递归
            sort(arr, start, mid);
            // 中间至结束，为一个数组，进行递归
            sort(arr, mid+1, end);
            // 归并两个左右两个数组
            marge(arr, start, mid, end);
        }
        return arr;
    }

    /**
     * 归并排序
     * @param arr
     * @param start 开始元素的下标
     * @param mid   中间，左开右闭，
     * @param end   结束元素的下标
     */
    public static void marge(int[] arr, int start, int mid, int end){
        // 需要创建一个新的数组容器
        int[] tempArr = new int[end-start+1];
        // 定义下标
        int i = start;
        int j = mid+1;
        // 定义容器的下标
        int index = 0;
        while (i<=mid && j<=end){
            if(arr[i]<=arr[j]){
                tempArr[index] = arr[i];
                i++;
            }else {
                tempArr[index] = arr[j];
                j++;
            }
            index++;
        }
        // 查看还有哪部分没有遍历完
        while (i<=mid){
            tempArr[index] = arr[i];
            i++;
            index++;
        }
        while (j<=end){
            tempArr[index] = arr[j];
            j++;
            index++;
        }
        // 还要将排序好的临时容器中的数，放回到原数组中
        for (int k = 0; k < tempArr.length; k++) {
            arr[start+k] = tempArr[k];
        }
    }

}
